package binary_tree.leetcode;

/**
 *  按中序遍历将一棵树重新排列为一棵递增顺序搜索树(每个结点只有右结点,没有左结点)
 * @Author Stark
 * @Date 2022/3/3 15:25
 */
public class Num897_IcreasingBST {
    public TreeNode increasingBST(TreeNode root) {
        if(root == null){
            return null;
        }
        //递归找到最左侧的结点
        TreeNode leftHead = increasingBST(root.left);
        TreeNode leftTail = leftHead;
        //leftTail从递增BST开头往后移动,找到尾节点
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        //尾节点不为空,则连接根结点
        if(leftTail != null) {
            leftTail.right = root;
            root.left = null;
        }
        //递归右结点,重复递归过程
        TreeNode rightHead = increasingBST(root.right);
        //中序遍历的右结点,连接右结点
        if(rightHead != null){
            root.right = rightHead;
            rightHead.left = null;
        }
        //如果左结点为空则返回根节点
        return leftHead == null ? root : leftHead;
    }
}
